package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname EditDistance
 * @Description Leetcode 72 编辑距离 难度 困难 动态规划 应该再做 字符串类的动态规划
 * @Date 2021/10/2 16:20
 * @Version 1.0
 */
public class EditDistance {


    /**
     * @param word1
     * @param word2
     * @return
     */
    public int minDistance(String word1, String word2) {

        int m = word1.length();
        int n = word2.length();


        //如果有一个字符串为空 则返回值为非空
        if (m == 0 || n == 0) {

            return m == 0 ? n : m;
        }

        //设置动态数组
        int[][] dp = new int[m + 1][n + 1];

        //对初始状态进行赋值
        //如果word2为空,word2删除
        for (int i = 0; i < m + 1; i++) {
            dp[i][0] = i;
        }

        //如果word1为空，word1添加
        for (int i = 0; i < n + 1; i++) {
            dp[0][i] = i;
        }


        for (int i = 1; i < m + 1; i++) {

            for (int j = 1; j < n + 1; j++) {


                //如果相同
                if (word1.charAt(i - 1) == word2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1];

                } else {
                    //增删改查
                    //word1增加 dp[i][j-1]  word2删除[i-1][j]  替换[i-1][j-1]
                    dp[i][j] = Math.min(Math.min(dp[i][j - 1], dp[i - 1][j]), dp[i - 1][j - 1]) + 1;

                }
            }
        }


        return dp[m][n];
    }

    public static void main(String[] args) {
        EditDistance editDistance = new EditDistance();
        int i = editDistance.minDistance("horse", "ros");
        System.out.println(i);
    }
}
